package com.leetcode;


/**
 * 十进制表达中1的个数
 *
 */
public class LeetCodeOffer43 {

	public static void main(String[] arg0) {
		int n = 111;

		int result = 0;

		String testStr = String.valueOf(n);
		int length = testStr.length();

		if (length == 1) { // test只是个位数
			if (n > 0) {
				result = 1;
			}
		} else {
			// 想用counts记录的n位数所包含1的个数
			int[] counts = new int[length - 1];
			for (int j = 0; j < length - 1; j++) {
				// 代表当前位数所有1的个数，例如1位数就1个1, 两位数共有19个1, 三位数共有271个1, 以此类推
				if (j == 0) {
					counts[j] = 1;
				} else {
					counts[j] = counts[j - 1] * 10 + (int) Math.pow(10, j);
				}
			}

			int tmpTest = n;
			for (int i = length; i >= 1; i--) {
				System.out.println("i = " + i + ", tmpTest  = " + tmpTest);
				if (i == 1) {
					if (tmpTest > 0) {
						result += 1;
					}
					break;
				}

				// a代表每一位上的数是几，从最高位到个位
				int chushu = (int) Math.pow(10, i - 1);
				int a = (int) (tmpTest / chushu);
				// 还有a==0的情况
				if (a == 0) {
					continue;
				}
				int yu = 0;
				if (a == 1) { // 如果这一位是1，后面有多少余数就记多少个1，而且还要加1后面都是0的那一种情况
					yu = (int) (tmpTest % chushu) + 1;
				} else {
					yu = chushu;
				}
				result += yu;

				int lowCount = counts[i - 2] * a;
				result += lowCount;

				tmpTest = tmpTest - a * chushu;
			}

		}

		System.out.println("1 到 " + n + "所有数中1的个数  = " + result);
	}

}
